//
// Created by madison on 2022/8/26.
// 多数元素

#include "vector"
#include "unordered_map"

using namespace std;

class Solution {
public:
    // 方法一：哈希表
    int majorityElement(vector<int> &nums) {
        unordered_map<int, int> counts;
        int majority = 0, cnt = 0;
        for (int num: nums) {
            ++counts[num];
            if (counts[num] > cnt) {
                majority = num;
                cnt = counts[num];
            }
        }
        return majority;
    }

    // 方法二：排序
    int majorityElement1(vector<int> &nums) {
        sort(nums.begin(), nums.end());
        return nums[nums.size() / 2];
    }

    // 方法五：Boyer-Moore 投票算法
    int majorityElement4(vector<int> &nums) {
        int candidate = -1;
        int count = 0;
        for (int num: nums) {
            if (num == candidate) {
                ++count;
            } else if (--count < 0) {
                candidate = num;
                count = 1;
            }
        }
        return candidate;
    }
};

int main() {
    return 0;
}
